#ifndef VECTORSSD_INDEX_H
#define VECTORSSD_INDEX_H

#include "../min_list/min_list.h"

#define PAGE_SIZE 16384
#define DiskANN_PAGE_SIZE 4096
#define ITER_LIMIT 100 //每个向量的最大迭代次数

//控制VectorSSD优化参数
#define CENTROID_ENTRY_SWITCH 1 //是否将聚类中心作为入口点加入候选列表，1开启0关闭
#define EXCULUSION_SWITCH 0 //是否开启提前驱逐，1开启0关闭
#define REDUC_FACTOR 0.0 //剩余距离=L2(Centroid, q) - REDUC_FACTOR*r
#define READ_PROB 0 //以多大的概率，即使被提前驱逐仍然读取出来检索。数值单位为%

//设置使用什么类型的visiting list
#define UTHASH 0
#define BLOOMFILTER 1
#define VISITING_LIST_TYPE BLOOMFILTER

//设置节点的格式
#define DISKANN_FORMAT 0x1
#define VECTORSSD_FORMAT 0x2

//设置minlist的节点状态
#define UNVISITED_FLAG  0b0001
#define VISITED_FLAG    0b0010

//设置DEBUG状态
#define DEBUG_WRITE_FILE 1

#define ASSERT_NULL_POINTER(ptr, message) \
    do { \
        if ((ptr) == NULL) { \
            printf("[ERROR!]%s in %s is NULL\n", message, __func__); \
            exit(EXIT_FAILURE); \
        } \
    } while(0)

//VectorSSD的头的格式，同时也是内存中用来维护索引文件的
typedef struct DiskANN_index
{
    unsigned long entry_count; //入口点的数量
    unsigned long entries_id[20]; //入口点的id，数量写死了方便读取，可以按需扩展

    unsigned long total_vectors; 
    unsigned long dim;
    unsigned long neighbor_count;
    unsigned long bytes_per_dim; //每个特征的大小
    unsigned long bytes_per_vector;
    unsigned long vector_per_block;
    unsigned long total_index_file_size;
    unsigned long block_size;    //索引文件的块大小，不是磁盘的块大小
    unsigned long flag; //标志位，用于标识例如是否包含了邻居的聚类
} INDEX_HEAD;

extern void print_DiskANN_index(INDEX_HEAD* head);
extern void destory_DiskANN_index(INDEX_HEAD* head);

//加载索引文件的头，不读取实际向量
//需要为每个数据集定制一个该函数，尽量把与数据集相关的字段修改都在这个函数里面完成
//这个函数只在创建VectorSSD格式的索引程序中有用
extern int load_index_file_SIFT1M(FILE *fp, INDEX_HEAD* head);

//加载VectorSSD索引文件
//因为我们是直接按照struct DiskANN_index结构体写入的，所以只需要读出来进行一个类型转换就好了
extern int load_index_file_vectorssd(FILE *fp, INDEX_HEAD* head);

//**********************VectorSSD优化部分**************************
//**************排除列表，用于记录某个向量检索时已排除的聚类*************
typedef struct exclusion_list
{
    int count;  //表明聚类个数
    char* flag; //用于标记某个聚类是否已被排除。0表示无法排除1表示已排除。主要是避免反复计算
    float* remain_distance; //L2(c,q) - r，当cuteoff小于该值时即可排除该聚类下所有点
} EXCLUSION_LIST; 

extern EXCLUSION_LIST* create_exclusion_list(int count); //count是聚类数量
extern void destory_exclusion_list(EXCLUSION_LIST* list);
extern void print_exclusion_list(EXCLUSION_LIST* list, int limit);

extern int update_exclusion_list(EXCLUSION_LIST* list, float cuteoff); //根据当前的cuteoff更新排除表
extern int check_exclusion_list(EXCLUSION_LIST* list, unsigned short cid);

extern int exclusion_list_count(EXCLUSION_LIST* list); //返回有多少个排除了的
//************************从磁盘读取聚类信息*************************
typedef struct cluster_info_entry
{
    int nearest_id;
    int farest_id;
    float nearest_distance;
    float farest_distance;
} CLUSTER_INFO_ENTRY; 

typedef struct cluster_info
{
    int count; //聚类数量
    int dim; //维数，从head中拷贝过来
    CLUSTER_INFO_ENTRY* entries; //保存各个聚类的最近最远信息
    float* centroid_feature; //存储各个聚类的中心向量
} CLUSTER_INFO; 

extern CLUSTER_INFO* create_load_cluster_info(char* centroid_path, char* centroid_info_path, int dim); //传入中心点和中心点信息的路径，直接在该函数完成加载。整个程序只需要执行一次该函数
extern int init_query(CLUSTER_INFO* cluster_info, EXCLUSION_LIST* exclusion_list, MINLIST* minlist, float* query, FILE* fp, INDEX_HEAD* head); //计算每个聚类与查询的距离并更新到排除列表中,并且把最近的聚类写入到minlist中初始化查询
extern void destory_cluster_info(CLUSTER_INFO* cluster_info);

//**********************加载数据集的相关函数**************************
typedef struct vector_float_array
{
    int dim;  //所存储的向量的维数
    int size; //features字段内包含了多少个向量，初始化时由参数指定
    float* features; //指向向量特征
} VECTOR_FLOAT_ARRAY; //存储一个向量数组。主要是为了避免多次读取

extern VECTOR_FLOAT_ARRAY* create_vector_float_array(FILE *fp, int size);
extern int read_vector_float_array_fromfile(FILE *fp, int start_vector, int count, VECTOR_FLOAT_ARRAY* array);
extern float* get_vector_float(VECTOR_FLOAT_ARRAY* array, int index);
extern void destory_vector_float_array(VECTOR_FLOAT_ARRAY* buf);
extern void print_vector_float(float* vector, int dim);

//**********************加载groundtruth文件的相关函数**************************
typedef struct gt_array
{
    int offset_factor; //读取文件时的偏移量，这个数字=文件内每个向量有多少个正确结果，主要用于读取文件时计算偏移用
    int count; //这个结构内包含了多少个向量的gt结果，初始化时由参数指定
    int k; //gts里面包含了前多少个正确结果，由参数指定
    unsigned int* gts; //指向结果
} GT_ARRAY; //存储一个向量数组的gt结果。主要是为了避免多次读取以及批量对比

extern GT_ARRAY* create_gt_array(FILE *fp, int k, int count);
extern int read_gt_array_fromfile(FILE *fp, int start_vector, int count, GT_ARRAY* array);
extern unsigned int* get_gt(GT_ARRAY* array, int index);
extern void print_gt_array(unsigned int* array, int k);
extern void print_gt_array_cluster(unsigned int* array, int k, unsigned short* clusters); //打印包含每个向量的聚类的结果
extern void destory_gt_array(GT_ARRAY* array);

//**********************存储ANN检索结果的结构**************************
typedef struct ann_result
{
    int k; //每项结果包含多少个最近邻居
    int count; //里面包含了多少项结果
    unsigned int* ids;
    float* distances;
    int* flag; //用于标记，和minlist保持一致
    //下面的是一些用于统计性能的指数
    unsigned int* iter_count; //最终迭代次数
    float* recall; //召回率
    unsigned int* io_count;
    unsigned int* exclusion_count; //这个是统计检索过程中有多少个排除的
    unsigned int* exclusion_list_count; //这个是统计检索结束，排除列表有多少个排除的
    unsigned int total_check_visited_list_count;
    unsigned int bloom_error_count;
} ANN_RESULT;

extern ANN_RESULT* create_ann_result(int k, int count);
extern unsigned int* get_ann_result_ids(ANN_RESULT* result, int index);
extern float* get_ann_result_distances(ANN_RESULT* result, int index);
extern int* get_ann_result_flags(ANN_RESULT* result, int index);
extern void print_ann_result(ANN_RESULT* result, int print_detail);
extern void destory_ann_result(ANN_RESULT* result);

//**********************核心检索函数**************************
extern int vectorssd_disk_search(FILE *fp, INDEX_HEAD* head, VECTOR_FLOAT_ARRAY* query_array, int k, int calculate_k, ANN_RESULT* result, CLUSTER_INFO* cluster_info, FILE* debug_file);

//**********************结果计算函数**************************
//k不一定要和ann_result的长度一样，可以计算例如recall-1@10。
extern float calculate_recall(GT_ARRAY* gt_array, ANN_RESULT* ann_result, int k);

//**********************向量格式和处理函数,DiskANN和VectorSSD通用该结构，区别就是Clusters是否置位**************************
typedef struct node_float
{
    void* buf; //指向读取到的原始向量数据。其他的字段都是基于该字段的偏移。只需要给这个字段分配空间即可
    float* features; //指向向量特征
    unsigned int* neighbors; //指向邻居列表
    unsigned short* clusters; //指向每个邻居的聚类，长度和neighbors一样
} NODE_FLOAT;

//根据之前读取到的DiskANN_index信息，创建、初始化一个向量并返回
extern NODE_FLOAT* create_node_float_buffer(INDEX_HEAD* head, int format);

//根据id从disk.index里面读取向量.buf的空间需要自己分配
//head需要首先通过load_index_file_SIFT1M读取
extern int read_node_float_fromfile(FILE *fp, INDEX_HEAD* head, unsigned int vid, NODE_FLOAT* vector);

//销毁向量
extern void destroy_node_float(NODE_FLOAT* vector);

extern void print_node_float(INDEX_HEAD* head, NODE_FLOAT* vector);

#endif